package com.dh.leetcode.seven;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

/**
 * @ClassName: _767_reorganize_string
 * @Description: 767. 重构字符串
 * 给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
 *
 * 若可行，输出任意可行的结果。若不可行，返回空字符串。
 *
 * 示例 1:
 *
 * 输入: S = "aab"
 * 输出: "aba"
 * 示例 2:
 *
 * 输入: S = "aaab"
 * 输出: ""
 * 注意:
 *
 * S 只包含小写字母并且长度在[1, 500]区间内。
 * <p>
 * https://leetcode-cn.com/problems/reorganize-string/
 * @Author: shouzimu
 * @Date: 2020/11/30 8:51
 */
public class _767_reorganize_string {

    /**
     * 隔一个插一个
     * @param S
     * @return
     */
    public String reorganizeString(String S) {
        char[] array = S.toCharArray();
        int len = 26;
        int[] bucket = new int[len];
        for (char c : array) {
            bucket[c - 'a']++;
        }
        int sLength = S.length();
        char[] res = new char[sLength];
        int maxIndex = 0;
        int max = 0;
        int threshold = (sLength + 1) >> 1;
        for (int i = 0; i < len; i++) {
            if (bucket[i] > max) {
                max = bucket[i];
                if (max > threshold) {
                    return "";
                }
                maxIndex = i;
            }
        }
        int index = 0;
        while (bucket[maxIndex]-- > 0) {
            res[index] = (char) (maxIndex + 'a');
            index += 2;
        }

        for (int i = 0; i < len; i++) {
            while (bucket[i]-- > 0) {
                if (index >= sLength) {
                    index = 1;
                }
                res[index] = (char) (i + 'a');
                index += 2;
            }
        }

        return new String(res);
    }

    public String reorganizeString3(String S) {
        char[] array = S.toCharArray();
        Arrays.sort(array);
        //转成List + 栈的结构
        List<Stack<Character>> list = new ArrayList<>();
        char prev = array[0];
        Stack<Character> prevStack = new Stack<>();
        for (char c : array) {
            if (c != prev) {
                prev = c;
                list.add(prevStack);
                prevStack = new Stack<>();
            }
            prevStack.push(c);
        }
        list.add(prevStack);
        list.sort(Comparator.comparing(t1 -> 0 - t1.size()));

        StringBuilder res = new StringBuilder();
        int listLength = list.size();

        int lastIndex = -1;
        for (int i = 0; i < listLength; i++) {
            Stack<Character> stack = list.get(i);
            while (!stack.isEmpty()) {
                char current = stack.peek();
                if (lastIndex != i) {
                    res.append(current);
                    stack.pop();
                }
                boolean swap = false;
                for (int j = i + 1; j < listLength; j++) {
                    Stack<Character> nextStack = list.get(j);
                    if (!nextStack.isEmpty()) {
                        char c = nextStack.peek();
                        if (c == current) {
                            continue;
                        }
                        res.append(nextStack.pop());
                        swap = true;
                        lastIndex = j;
                        break;
                    }
                }
                if (!swap && !stack.isEmpty()) {
                    return "";
                }
            }
        }
        return res.toString();
    }

    /**
     * 限定26字符桶排序
     * <p>
     * 执行有问题
     * <p>
     * 先按数量排，再按字符顺序排
     *
     * @param S
     * @return
     */
    public String reorganizeString2(String S) {
        char[] array = S.toCharArray();
        int len = 26;
        int[] bucket = new int[len];
        for (char c : array) {
            bucket[c - 'a']++;
        }

        int index = 0;

        while (index < S.length()) {
            int retry = 0;
            for (int i = 0; i < len; i++) {
                if (bucket[i] != 0) {
                    char current = (char) ('a' + i);
                    if (index > 1 && current == array[index - 1]) {
                        if (retry == 0) {
                            retry++;
                            continue;
                        } else {
                            return "";
                        }
                    }
                    array[index] = current;
                    index++;
                    bucket[i]--;
                }
            }
        }
        return new String(array);
    }

    @Test
    public void reorganizeStringTest() {
        String s = "hellohex";
        String s2 = "hex";
        System.out.println(s.indexOf(s2));

        char[] a =   "cmcmcmcbboogiklstwxz".toCharArray();
        Arrays.sort(a);
        char[] b = "cocgcickmlmsmtbwbxoz".toCharArray();
        Arrays.sort(b);
        char[] c = "ogccckcwmbmxtsbmozli".toCharArray();
        Arrays.sort(c);

        Assert.assertArrayEquals(a, b);
        Assert.assertArrayEquals(a, c);

        Assert.assertEquals("bfbrs", reorganizeString("tndsewnllhrtwsvxenkscbivijfqnysamckzoyfnapuotmdexzkkrpmppttficzerdndssuveompqkemtbwbodrhwsfpbmkafpwyedpcowruntvymxtyyejqtajkcjakghtdwmuygecjncxzcxezgecrxonnszmqmecgvqqkdagvaaucewelchsmebikscciegzoiamovdojrmmwgbxeygibxxltemfgpogjkhobmhwquizuwvhfaiavsxhiknysdghcawcrphaykyashchyomklvghkyabxatmrkmrfsppfhgrwywtlxebgzmevefcqquvhvgounldxkdzndwybxhtycmlybhaaqvodntsvfhwcuhvuccwcsxelafyzushjhfyklvghpfvknprfouevsxmcuhiiiewcluehpmzrjzffnrptwbuhnyahrbzqvirvmffbxvrmynfcnupnukayjghpusewdwrbkhvjnveuiionefmnfxao"));
        Assert.assertEquals("cmcmcmcbobogiklstwxz", reorganizeString("cmcmcmcbboogiklstwxz"));
        Assert.assertEquals("ababa", reorganizeString("baaba"));
        Assert.assertEquals("vlvov", reorganizeString("vvvlo"));
        Assert.assertEquals("aba", reorganizeString("aab"));
        Assert.assertEquals("", reorganizeString("aaab"));
        Assert.assertEquals("bfbrs", reorganizeString("bfrbs"));
    }

}
